package BackTracking;

import java.util.ArrayList;
import java.util.Arrays;

public class 剑指Offer38字符串的排列 {

    ArrayList<String> res = new ArrayList<>();
    StringBuffer sb = new StringBuffer();

    public String[] permutation(String s) {
        char[] ch = s.toCharArray();
        boolean[] used = new boolean[s.length()];
        // 将ch数组中的字符排序，方便后面回溯时的去重处理
        Arrays.sort(ch);
        backtracking(ch, used);
        return res.toArray(new String[0]);
    }

    void backtracking(char[] ch, boolean[] used){
        // 如果将所有字符都使用上，表示回溯完成
        if (ch.length == sb.length()){
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < ch.length; i++) {
            // i > 0防止越界【如果当前字符和上一个字符相同，且上一个字符使用过，则直接做剪枝处理】
            // 或者当前字符使用过，也要做剪枝处理
            if (i > 0 && ch[i] == ch[i - 1] && used[i - 1] || used[i]) continue;
            // 满足条件【添加字符，并标记为已近使用过】
            sb.append(ch[i]);
            used[i] = true;
            backtracking(ch, used);
            // 回溯【删除掉刚刚添加的字符，重新标记字符为未使用】
            used[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
